package com.blb.suanfa;

import sun.reflect.generics.tree.Tree;

import javax.swing.tree.TreeNode;

/**
 * 二叉查找数
 */
public class BinarySearchTree {

    //树节点
    static class TreeNode {
        Integer data;
        TreeNode left;
        TreeNode right;

        public TreeNode(Integer data, TreeNode left, TreeNode right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }

        public TreeNode() {
        }
    }

    //根节点
    private TreeNode root;
    //节点数
    private int size = 0;

    //添加树节点
    public void add(Integer data){
        if(root == null){
            //如果树为空创建根节点
            root = new TreeNode(data,null,null);
            size++;
        }else{
            TreeNode current = root;
            while (true){
                if (data < current.data){
                    if(current.left == null){
                        current.left = new TreeNode(data,null,null);
                        size++;
                        break;
                    }else{
                        current = current.left;
                    }
                }else if(data > current.data){
                    if(current.right == null){
                        current.right = new TreeNode(data,null,null);
                        size++;
                        break;
                    }else{
                        current = current.right;
                    }
                }else{
                    throw new RuntimeException("不允许相同的数据存在");
                }
            }
        }
    }

    /**
     * 前序遍历(中左右）
     * @param node
     */
    public void preShow(TreeNode node){
        if(node == null){
            return;
        }
        //输出中间节点
        System.out.println(node.data);
        //遍历左孩子
        middleShow(node.left);
        //遍历右孩子
        middleShow(node.right);
    }

    /**
     * 中序遍历(左中右）
     * @param node
     */
    public void middleShow(TreeNode node){
        if(node == null){
            return;
        }
        //遍历左孩子
        middleShow(node.left);
        //输出中间节点
        System.out.println(node.data);
        //遍历右孩子
        middleShow(node.right);
    }

    /**
     * 后序遍历(左右中）
     * @param node
     */
    public void afterShow(TreeNode node){
        if(node == null){
            return;
        }
        //遍历左孩子
        middleShow(node.left);
        //遍历右孩子
        middleShow(node.right);
        //输出中间节点
        System.out.println(node.data);
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.add(8);
        tree.add(9);
        tree.add(2);
        tree.add(3);
        tree.add(1);
        System.out.println("中序");
        tree.middleShow(tree.root);
        System.out.println("前序");
        tree.preShow(tree.root);
        System.out.println("后序");
        tree.afterShow(tree.root);
    }
}
